
//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
     * 第一遍
     * @param head
     * @param n
     * @return
     */
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        ListNode dummy = new ListNode(-1);
//        dummy.next = head;
//
//        // 删除倒数第n个，要先找到倒数第n+1个节点
//        ListNode x = findFromEnd(dummy, n+1);
//        x.next = x.next.next;
//        return dummy.next;
//    }
//    ListNode findFromEnd (ListNode head,int k){
//        // 返回链表的倒数第k个节点
//        ListNode p1 = head;
//        // p1先走k步
//        for (int i = 0; i < k; i++) {
//            p1 = p1.next;
//        }
//        ListNode p2 = head;
//        // p2走n-k步；
//        while (p1 != null) {
//            p1 = p1.next;
//            p2 = p2.next;
//        }
//        // p2指向第n-k个节点，所以也就是它就是倒数第k个节点
//        return p2;
//    }


    /**
     * 第二遍
     * @param head
     * @param n
     * @return
     */
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        ListNode dummy = new ListNode(-1);
//        dummy.next = head;
//
//        // 删除倒数第n个节点，必须知道倒数n+个节点位置，才好删除
//        ListNode x = findEndNode(dummy, n+1);
//        x.next = x.next.next;
//        return dummy.next;
//    }
//
//
//    ListNode findEndNode(ListNode head, int k) {
//        ListNode p1 = head;
//        ListNode p2 = head;
//
//        // p1走k步
//        for (int i = 0; i < k; i++) {
//            p1 = p1.next;
//        }
//        // p1和p2各走
//        while (p1 != null) {
//            p1 = p1.next;
//            p2 = p2.next;
//        }
//        return p2;
//    }


    /**
     * 第三遍 2/27
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 找到倒数第n+1个节点
        ListNode newNode = findEndNode(dummy, n + 1);
        newNode.next = newNode.next.next;
        return dummy.next;
    }

    ListNode findEndNode(ListNode head, int k) {
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 0; i < k; i++) {
            // p先走k步
            p1 = p1.next;
        }

        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
